# [1,5,2,4,3]

memo = dict()


def fun(nums, i):
    if i in memo:
        return memo[i]
    if i == (len(nums) - 1):
        return 1
    else:
        max_len = 1
        for j in range(i + 1, len(nums)):
            if nums[i] < nums[j]:
                max_len = max(max_len, fun(nums, j) + 1)
        memo[i] = max_len
        return max_len


def get_long(nums):
    return max([fun(nums, i) for i in range(len(nums))])


def dp(nums: list):
    L = [0 for i in range(len(nums))]
    L[len(nums) - 1] = 1
    for i in reversed(range(len(nums))):
        for j in range(i + 1, len(nums)):
            if nums[j] > nums[i]:
                L[i] = max(L[i], L[j] + 1)
    return max(L)


nums = [1, 5, 2, 4, 3, 5, 848, 455, 1, 51, 351, 51, 31, 531, 35, 153, 15, 16, 3, 151]
print(dp(nums))
